题目分析

这是一位热心的小伙伴给我分享的题目，这个题目难度不大，但是给的例子具有一定的迷惑性，一分钟我就想到了思路，但是没有做对，后来才发现错误的原因。

最小堆

假设三个数字为a < b < c,那么最终和一定为a+b+c。如果先算a + b，那么时间为a + b，再算(a + b) + c，时间为(a + b) + ((a + b) + c)，一共为2 x a + 2 x b + c。其他的加法顺序都会导致结果变大。

我的思路是，数字小的先加，因为先加的会重复多次，所以是最优的解法。

一开始，我就将数字排序，从最小加到最大。结果出现了问题，最后发现原因是被题目的样例骗了。如果样例是2, 2, 2, 2就会想到正确的计算方式了。按照我的计算是2 + 2 = 4, 时间为4，4 + 2 = 6，时间为4 + 6 = 10, 6 + 2 = 8, 时间为10 + 8 = 18。然而正确的顺序是2 + 2 = 4，时间为4, 再算后面两个2 + 2 = 4，时间为4 + 4 = 8, 4 + 4 = 8, 时间为8 + 8 = 16。

因此不能直接排序，从小加到大，因为有可能在计算的过程中产生了较大的值，这样可以计算其他元素中最小的两个值之和。所以要用最小堆的思想计算，每次取出两个最小值。

算法的**时间复杂度为$O(nlog(n))$，空间复杂度为$O(n)$**。

import java.util.PriorityQueue;

public class Solution {
    public long calc(int[] nums) {
        PriorityQueue<Long> heap = new PriorityQueue<>();
        for (int val : nums) {
            heap.add((long) val);
        }
        long res = 0;
        while (heap.size() > 1) {
            long valA = heap.poll();
            long valB = heap.poll();
            long valC = valA + valB;
            res += valC;
            heap.add(valC);
        }
        return res;
    }
}

刷题总结

面试题和Leetcode的题目最大的差异是面试题的样例非常少，有的题目甚至只有一个样例，可能会误导你的思想，但是Leetcode的题目做错了会显示错误样例，能起到一定的检查效果。这也要求面试时，同学们一定要细心，认真，多想一想算法的完备性。